#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>

using namespace std;
inline int getRow(int n,int i)
{
  return i/n;
}
inline int getColumn(int n,int i)
{
  return i%n;

}
bool searchMatrix(vector<vector<int>>& matrix, int target) 
{
  
  int m = matrix.size();
  int n = matrix[0].size();

  if(m<1||n<1)
    return false;

  const int imax = m*n-1;
  int front = 0;
  int back = imax;
  int mid = (front+back)/2;
  int i=0;
  int j=0;

  while ( front<=back )
  {
    mid = (front+back)/2;
    i = getRow(n,mid);
    j = getColumn(n,mid);

    if ( matrix[i][j]==target )
      return true;

    if  ( matrix[i][j]<target )
      front = mid+1;
    else 
      back = mid-1;
  }

  return false;

}



int main(int argc,char *argv[])
{

  vector< vector<int> >  matrix;
  matrix.push_back( vector<int> {1,3,5,7} );
  matrix.push_back( vector<int> {10,11,16,20} );
  matrix.push_back( vector<int> {23,30,34,50} );



  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  //func();
  bool ret=searchMatrix(matrix,3);

  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming:" << tv2.tv_usec - tv1.tv_usec <<"us"<< endl;
  cout<<"ret:"<<ret<<endl;



  return 0;
}
